home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / sys / amiga / programmer / 5801 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.4 KB
  1. Path: hearst.acc.Virginia.EDU!adastra!mbs
  2. Newsgroups: comp.sys.amiga.programmer
  3. From: mbs@adastra.cvl.va.us (Michael B. Smith)
  4. Subject: Re: Sorting a list
  5. References: <272.6650T63T1340@sn.no> <314E9DCA.2E9E@cs.ruu.nl>
  6. X-NewsReader: GRn 3.0f March 8, 1996
  7. MIME-Version: 1.0
  8. Content-Type: text/plain; charset=iso-8859-1
  9. Content-Transfer-Encoding: 8bit
  10. Message-ID: <mbs.4a6m@adastra.cvl.va.us>
  11. Date: Wed, 20 Mar 96 07:11:50 EDT
  12. Organization: Only if you insist...
  13.  
  14. > Christopher Naas wrote:
  15. > > What's the absolutely fastest algorithm for sorting a List with around 1000
  16. > > items alphabetically?
  17.  
  18. I went through a fairly exhaustive search around a year ago, to try
  19. to find ways to significantly speed up GRn sorting. I found the
  20. quickest practical way (without significant setup and teardown time)
  21. to be an iterative quicksort.
  22.  
  23. void
  24. SortList (struct List *list)
  25. {
  26.     int
  27.         count = CountListEntries (list);
  28.     struct Node
  29.         **n;
  30.  
  31.     PROC ("SortList");
  32.  
  33.     if (count < 2)
  34.     {
  35.         D (("exit, count %ld\n", count));
  36.         return;
  37.     }
  38.  
  39.     n = AllocVec (count * sizeof (struct Node *), 0);
  40.     if (!n)
  41.     {
  42.         /* gulp! */
  43.         D (("exit, couldn't allocate %ld bytes\n", count * sizeof (struct Node *)));
  44.         return;
  45.     }
  46.  
  47.     SetupList (list, n, count);
  48.     qsort (n, count, sizeof (struct Node *), CompareName);
  49.     FixArray (list, n, count);
  50.  
  51.     FreeVec (n);
  52.  
  53.     D (("exit\n"));
  54.     return;
  55. }
  56.  
  57. --
  58.   //   Michael B. Smith
  59. \X/    mbs@adastra.cvl.va.us
  60.